
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1712. -- [Usaco2007 China]Summing Sums -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1712: [Usaco2007 China]Summing Sums</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>110&nbsp;&nbsp;<span class=green>Solved: </span>37<br>[<a href='submitpage.php?id=1712'>Submit</a>][<a href='problemstatus.php?id=1712'>Status</a>][<a href='bbs.php?id=1712'>Discuss</a>]</center><h2>Description</h2><div class=content>
The N (1 <= N <= 50,000) cows, conveniently numbered 1..N, are
trying to learn some encryption algorithms. After studying a few
examples, they have decided to make one of their own! However, they
are not very experienced at this, so their algorithm is very simple:

Each cow i is given a starting number C_i (0 <= C_i < 90,000,000),
and then all the cows perform the following process in parallel:

    * First, each cow finds the sum of the numbers of the other N-1
      cows.

    * After all cows are finished, each cow replaces her number
      with the sum she computed. To avoid very large numbers, the
      cows will keep track of their numbers modulo 98,765,431.

They told Canmuu the moose about it in November; he was quite
impressed.

Then one foggy Christmas Eve, Canmuu came to say:

    "Your algorithm is too easy to break! You should repeat it T
     (1 <= T <= 1,414,213,562) times instead."

Obviously, the cows were very frustrated with having to perform so
many repetitions of the same boring algorithm, so after many hours
of arguing, Canmuu and the cows reached a compromise: You are to
calculate the numbers after the encryption is performed!

*Some extra feedback will be provided for the first 10 submissions to this
problem.

</div><h2>Input</h2><div class=content>* Line 1: Two space-separated integers: N and T

* Lines 2..N+1: Line i+1 contains a single integer: C_i

</div><h2>Output</h2><div class=content>
* Lines 1..N: Line i contains a single integer representing the number
        of cow i (modulo 98,765,431) at the end of the encryption.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3 4<br />
1<br />
0<br />
4<br />
<br />
INPUT DETAILS:<br />
<br />
Three cows, with starting numbers 1, 0, and 4; four repetitions of the<br />
encryption algorithm.<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
26<br />
25<br />
29<br />
<br />
OUTPUT DETAILS:<br />
<br />
The following is a table of the cows' numbers for each turn:<br />
<br />
          Cows' numbers<br />
Turn    Cow1  Cow2  Cow3<br />
 0        1     0     4<br />
 1        4     5     1<br />
 2        6     5     9<br />
 3       14    15    11<br />
 4       26    25    29<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1712'>Submit</a>][<a href='problemstatus.php?id=1712'>Status</a>][<a href='bbs.php?id=1712'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
